﻿using System.Collections.Generic;

namespace h24
{
class TangGuo{
	public int MinTang(int [] arr){
		if(arr.Length == 1) return 1;
		if(arr.Length == 0) return 0;

		//Up Down
		//CompressSame to 2Point
		var lst = new List<int>();//0Normal 1 Top 2 Bottom 3相等
		for(var i = 0; i < arr.Length; i++){
			var v = arr[i];
			if(i > 0 && i < arr.Length-1){
				var pre = arr[i-1];
				var next = arr[i+1];
				if(v > pre && v > next){//top
					lst.Add(1);
				}else if(v < pre && v < next){//bottom
					lst.Add(2);
				}else {
					// if(v == pre || v == next) lst.Add(3);//邻居相等排解了
					// else lst.Add(0);
					if(v == pre && v == next) lst.Add(2);
					else if(v == pre && v > next){
						lst.Add(1);
					}else if(v == pre && v < next){
						lst.Add(2);
					}else if(v > pre && v == next){
						lst.Add(1);
					}else if(v < pre && v == next){
						lst.Add(2);
					}else {
						lst.Add(0); //斜坡上的元素
					}
				}
			}else if(i == 0){
				var next= arr[i+1];
				if(v > next) lst.Add(1);
				else if(v < next) lst.Add(2);
				else lst.Add(2); //bottom
			}else {
				var pre = arr[i-1];
				if(v > pre)lst.Add(1);
				else if(v < pre)lst.Add(2);
				else lst.Add(2); //bottom
			}
		}
		var assign = new List<int>();
		for(var i = 0; i < lst.Count; i++) assign.Add(0);
		//确定每个Top和两个Bottom的关系
		for(var i = 0; i < lst.Count; i++){
			var v = lst[i];
			var cn = arr[i];
			if(v == 2){//Bottom 两侧扩张
				assign[i] = 1;
				var curH = 2;
				for(var j = i-1; j >=0; j--){
					var jv = lst[j];
					if(jv == 1){//Top 不处理 是两侧的高度最大的+1
						var av = assign[j];
						if(curH > av){
							assign[j] = curH;
						}
						break;
					}
					if(jv == 0){//比我大
						assign[j] = curH++;
					}else {
						break;
					}
				}
				curH=2;
				for(var j = i+1; j < lst.Count; j++){
					var jv = lst[j];
					if(jv == 1){
						var av = assign[j];
						if(curH > av) assign[j] = curH;
						break;
					}
					if(jv != 0) break;
					assign[j] = curH++;
				}
			}else if(v == 1){
			}
		}
		var sumT = 0;
		foreach(var v in assign) 
			sumT += v;
		return sumT;
	}
}
public class Solution {
    public int Candy(int[] ratings) {
	    return new TangGuo().MinTang(ratings);
    }
}

}